home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 003 / phone.arc / PHONE.C next >
Encoding:
C/C++ Source or Header  |  1988-08-18  |  10.4 KB  |  432 lines
  1. /*
  2.  * phone.c
  3.  *
  4.  * Search a phone book file for an entry
  5.  *
  6.  * Author:        Martin Minow
  7.  * MSDOS version:    J. Anthony Movshon
  8.  *            7 August 1984
  9.  */
  10.  
  11. #include    <stdio.h>
  12. #include    <ctype.h>
  13.  
  14. #ifdef    isprint
  15. #ifndef    isgraph
  16. #define    isgraph(c)    (isprint(c) && c != ' ')
  17. #endif
  18. #endif
  19.  
  20. #define    TRUE        1
  21. #define    FALSE        0
  22. #define    EOS        0
  23.  
  24. #define    NFIELDS        100
  25. #define    LINESIZE    257
  26.  
  27. char        *search[NFIELDS];        /* search text        */
  28. char        *word[NFIELDS];            /* file text split up    */
  29. int        issoundex[NFIELDS];        /* TRUE for soundex    */
  30. unsigned int    hash[NFIELDS];            /* soundex hash value    */
  31. char        line[LINESIZE];            /* text line as read    */
  32. char        work[LINESIZE];            /* text line in words    */
  33. char        argtext[LINESIZE];        /* prompted text    */
  34. FILE        *fd;                /* Phone book file    */
  35.  
  36. /*
  37.  * This search list is used to locate the phone book.
  38.  */
  39.  
  40. static char    *searchlist[] = {
  41.     "phone.txt",
  42.     "\\etc\\phone.txt",
  43.     "e:\\etc\\phone.txt",
  44.     NULL
  45. };
  46.  
  47. /*
  48.  * Usage message
  49.  */
  50. static char    *helpmessage[] = {
  51. "Search phone book for an argument string:",
  52. "  '*' in a string matches any string of characters",
  53. "  '?' in a string matches any non-null character",
  54. "Any left-most match succeeds and multiple search arguments are permitted.",
  55. "Names that sound similar will be reported if '*' and '?' are not used.",
  56. NULL,
  57. };
  58.  
  59. main(argc, argv)
  60. int        argc;
  61. char        *argv[];
  62. {
  63.     openphonebook(argc, argv);
  64.     if (argc > 1) {
  65.         findargs(argc, argv);
  66.         setsoundexflag();
  67.         findmatch();
  68.     }
  69.     else {
  70.         /*
  71.          * No arguments were given.  Prompt and read
  72.          * arguments from standard input.
  73.          */
  74.         fprintf(stderr,
  75.         "Phonebook search program, <return> for help\n");
  76.         while (!feof(stdin)) {
  77.         fprintf(stderr, "Search: ");
  78.         fflush(stderr);
  79.         if (gets(argtext) == NULL)
  80.             break;
  81.         if (argtext[0] == EOS) {
  82.             usage();
  83.         }
  84.         else {
  85.             packtext(argtext, search);
  86.             setsoundexflag();
  87.             findmatch();
  88.             rewind(fd);
  89.         }
  90.         }
  91.     }
  92. }
  93. openphonebook(argc, argv)
  94. int        argc;        /* Arg count from operating system    */
  95. register char    *argv[];    /* Arg vector from operating system    */
  96. /*
  97.  * Open the phone book file -- exit to system if failure.
  98.  */
  99. {
  100.     register char    **namep;
  101.     register char    *cp;
  102.  
  103.     while (--argc > 0) {
  104.         cp = *++argv;
  105.         if (*cp++ == '-') {
  106.         if ((*cp == 'f' || *cp == 'F') && cp[1] == EOS) {
  107.             *argv++ = NULL;
  108.             cp = *argv;
  109.             if (--argc <= 0) {
  110.             fprintf(stderr, "-f must be followed by a file name\n");
  111.             exit(1);
  112.             }
  113.             else if ((fd = fopen(cp, "r")) == NULL) {
  114.             perror(cp);
  115.             fprintf(stderr, "phone: can't open your phonebook\n");
  116.             exit(1);
  117.             }
  118.             else {
  119.             *argv = NULL;
  120.             return;
  121.             }
  122.         }
  123.         }
  124.     }
  125.     /*
  126.      * On VMS, RSTS, RSX, or whathaveyou, try the search list
  127.      */
  128.     for (namep = searchlist; *namep != NULL; namep++) {
  129.         if (openit(*namep, FALSE))
  130.         return;
  131.     }
  132.     fprintf(stderr, "phone: can't locate phonebook phone.txt\n");
  133.     exit(1);
  134. }
  135.  
  136. static int
  137. openit(filename, fatal)
  138. char    *filename;        /* Actual filename to open        */
  139. int    fatal;            /* TRUE if failure is fatal        */
  140. /*
  141.  * Open the indicated file.  Return TRUE if success.  If failure and
  142.  * fatal is TRUE, exit to the operating system with an appropriate
  143.  * error message, else, return FALSE.
  144.  */
  145. {
  146.     if ((fd = fopen(filename, "r")) != NULL)
  147.         return (TRUE);
  148.     else if (!fatal)
  149.         return (FALSE);
  150.     else {
  151.         perror(filename);
  152.         fprintf(stderr, "phone: can't open phonebook\n");
  153.         exit(1);
  154.     }
  155. }
  156. findargs(argc, argv)
  157. int        argc;        /* Arg count from operating system    */
  158. char        *argv[];    /* Arg vector from operating system    */
  159. /*
  160.  * Build the search arguments in field[].
  161.  */
  162. {
  163.     register char        *cp;
  164.     register int        fieldindex;
  165.     register char        c;
  166.  
  167.     fieldindex = 0;
  168.     while (--argc > 0) {
  169.         cp = *++argv;
  170.         if (cp == NULL)
  171.         continue;
  172.         search[fieldindex] = cp;
  173.         while ((c = *cp) != EOS) {
  174.         *cp++ = tolower(c);
  175.         }
  176.         fieldindex++;
  177.     }
  178.     search[fieldindex] = NULL;        /* terminate the list    */
  179.     setsoundexflag();
  180. }
  181. setsoundexflag()
  182. /*
  183.  * Examine the search arguments (in search[]), setting issoundex[]
  184.  * appropriately.  If this argument should be "soundex'ed", calculate
  185.  * the hash value.
  186.  */
  187. {
  188.     register char        *cp;
  189.     register int        fieldindex;
  190.     register char        c;
  191.     extern unsigned int    soundex();
  192.  
  193.     for (fieldindex = 0; (cp = search[fieldindex]) != NULL; fieldindex++) {
  194.         issoundex[fieldindex] = TRUE;
  195.         while ((c = *cp++) != EOS) {
  196.         if (c == '*' || c == '?') {
  197.             issoundex[fieldindex] = FALSE;
  198.             break;
  199.         }
  200.         }
  201.         if (issoundex[fieldindex])
  202.         hash[fieldindex] = soundex(search[fieldindex]);
  203.     }
  204. }
  205. findmatch()
  206. /*
  207.  * Read the file, print matching lines.
  208.  */
  209. {
  210.     register int        fieldindex;    /* Field pointer    */
  211.     register char        **wp;        /* Word pointer        */
  212.     register int        matchcount;    /* Counts matches    */
  213.     extern unsigned int    soundex();
  214.  
  215.     matchcount = 0;
  216.     line[0] = EOS;
  217.     for (;;) {
  218.         if (line[0] == EOS && fgets(line, sizeof (line), fd) == NULL)
  219.         break;
  220.         if (isspace(line[0])) {
  221.         line[0] = EOS;            /* Force read next time    */
  222.         continue;
  223.         }
  224.         strcpy(work, line);
  225.         packtext(work, word);
  226.         for (fieldindex = 0; search[fieldindex] != NULL; fieldindex++) {
  227.         for (wp = word; *wp != NULL; wp++) {
  228.             if (issoundex[fieldindex] != FALSE
  229.              && soundex(*wp) == hash[fieldindex])
  230.             goto gotcha;
  231.             if (matchtest(*wp, search[fieldindex]))
  232.             goto gotcha;
  233.         }
  234.         }
  235.         line[0] = EOS;            /* Force read next time    */
  236.         continue;                /* Not found        */
  237.  
  238. gotcha:        matchcount++;
  239.         do {
  240.         fputs(line, stdout);
  241.         if (fgets(line, sizeof (line), fd) == NULL)
  242.             goto done;
  243.         } while (isspace(line[0]));
  244.     }
  245. done:    if (matchcount == 0)
  246.         fprintf(stderr,"phone: no match found\n");
  247. }
  248. packtext(text, wordlist)
  249. register char    *text;            /* This text line is packed    */
  250. register char    **wordlist;        /* Into this array of words    */
  251. /*
  252.  * Build wordlist.  Modifies text.
  253.  */
  254. {
  255.     register char        c;
  256.  
  257.     c = *text;
  258.     while (c != EOS) {
  259.         while ((c = *text) != EOS && !isgraph(c))
  260.         ++text;                /* Skip over whitespace    */
  261.         if (c == EOS)
  262.         break;
  263.         *wordlist++ = text;            /* Start of new word    */
  264.         while ((c = *text), isgraph(c))
  265.         *text++ = tolower(c);
  266.         *text++ = EOS;            /* Terminate the word    */
  267.     }
  268.     *wordlist = NULL;
  269. }
  270. int
  271. matchtest(name, pattern)
  272. register char    *name;        /* What to look for            */
  273. register char    *pattern;    /* May have wildcard            */
  274. /*
  275.  * Recursive routine to match "name" against "pattern".
  276.  * Returns TRUE if successful, FALSE if failure.
  277.  *
  278.  * pattern follows Dec filename wildcard conventions:  '*' matches any
  279.  * string (even null), '?' matches any single (non-null) byte.
  280.  *
  281.  */
  282. {
  283.     register char    pattbyte;
  284.  
  285.     for (;;) {
  286.         /* fprintf(stderr, "(%s) (%s), namebyte = '%c', pattbyte = '%c'\n",
  287.         name, pattern, *name, *pattern);
  288.         */
  289.         /*
  290.          * Assume that patterns are terminated -- implicitly --
  291.          * by '*', allowing all left-matches to succeed.
  292.          */
  293.         if ((pattbyte = *pattern++) == EOS
  294.          || (pattbyte == '*' && *pattern == EOS))
  295.         return (TRUE);
  296.         /*
  297.          * Not at end of the name string.
  298.          */
  299.         switch (pattbyte) {
  300.         case '*':            /* Wild card means "advance"    */
  301.         do {
  302.             if (matchtest(name, pattern))
  303.             return (TRUE);
  304.         } while (*name++ != EOS);
  305.         return (FALSE);        /* Did our best            */
  306.  
  307.         case '?':            /* One byte joker        */
  308.         break;            /* succeeds with this byte    */
  309.  
  310.         default:            /* Others much match exactly    */
  311.         if (*name != pattbyte)
  312.             return (FALSE);
  313.         break;
  314.         }
  315.         name++;            /* Advance name byte        */
  316.     }
  317. }
  318. /*
  319.  * soundex(string)
  320.  *
  321.  * Return the soundex hash value for the argument string.
  322.  * S_V should be zero for efficiency.
  323.  */
  324.  
  325. #define    S_V    0    /* Vowels: a e i o u (maybe y, h, w)        */
  326. #define    S_SK    1    /* "hard" consonants: s c z x k q        */
  327. #define    S_TD    2    /* Dental stops: t d                */
  328. #define    S_FV    3    /* f v                         */
  329. #define    S_GJ    4    /* g j                        */
  330. #define    S_B    5    /* b                        */
  331. #define    S_L    6    /* l                        */
  332. #define    S_M    7    /* m                        */
  333. #define    S_N    8    /* n                        */
  334. #define    S_P    9    /* p                        */
  335. #define    S_R    10    /* r                        */
  336. #define    S_MAX    11    /* "radix" of soundex values            */
  337.  
  338. /*
  339.  * The following are the hash values for each letter.
  340.  */
  341.  
  342. static char    sx_letters[] = {
  343. /*     a     b     c     d     e     f     g     h    */
  344.     S_V,    S_B,    S_SK,    S_TD,    S_V,    S_FV,    S_GJ,    S_V,
  345. /*     i     j     k     l     m     n     o     p    */
  346.     S_V,    S_GJ,    S_SK,    S_L,    S_M,    S_N,    S_V,    S_P,
  347. /*     q     r     s     t     u     v     w     x    */
  348.     S_SK,    S_R,    S_SK,    S_TD,    S_V,    S_FV,    S_V,    S_SK,
  349. /*     y     z                            */
  350.     S_V,    S_SK,
  351. };
  352.  
  353. /*
  354.  * The first letter of the following consonant pairs is silent.
  355.  */
  356.  
  357. static char    *sx_leading_silent = "tstzghknpnptpf";
  358.  
  359. unsigned int
  360. soundex(string)
  361. register char        *string;
  362. /*
  363.  * Compute the soundex hash for the argument string.
  364.  * -- somewhat modified from the original algorithm.
  365.  * "Margaret K. Odell and Robert C. Russell.  U.S.
  366.  * patents 1261167 (1918) and 1435663 (1922)."  as
  367.  * reprinted in Donald Knuth, Sorting and Searching.
  368.  */
  369. {
  370.     register int    c;    /* Current character            */
  371.     register char    *sxp;    /* -> leading silent string        */
  372.     int        last;    /* Previous character for doubles    */
  373.     int        next;    /* Next character in the string        */
  374.     int        value;    /* Soundex value            */
  375.     int        temp;    /* Hash for this character        */
  376.     int        count;    /* Want only three digits        */
  377.  
  378.     while (c = *string++, !isalpha(c)) {
  379.         if (c == EOS)
  380.         return (0);
  381.     }
  382.     last = c = tolower(c);
  383.     value = c - 'a' + 1;    /* Initial hash == first letter value    */
  384.     next = *string++;
  385.     next = tolower(next);
  386.     count = 3;        /* Maximum times through this loop    */
  387.     while (--count >= 0 && (c = next) != EOS) {
  388.         next = *string++;
  389.         next = tolower(next);
  390.         if (next != EOS) {
  391.         /*
  392.          * Ignore the first letter in a silent-pair.
  393.          */
  394.         for (sxp = sx_leading_silent; *sxp != EOS; sxp++) {
  395.             if (*sxp++ == c && *sxp == next) {
  396.             goto reject;    /* reject silent first letter    */
  397.             }
  398.         }
  399.         /*
  400.          * Change 'ph' to 'f'
  401.          */
  402.         if (c == 'p' && next == 'h') {
  403.             c = 'f';
  404.             next = *string++;
  405.             next = tolower(next);
  406.         }
  407.         }
  408.         if (islower(c)) {
  409.         if ((temp = sx_letters[c - 'a']) != S_V && c != last) {
  410.             value *= S_MAX;
  411.             value += temp;
  412.         }
  413.         last = c;
  414.         }
  415. reject:    ;                /* Jump here on silent pairs    */
  416.     }
  417.     while (--count >= 0)        /* Finish off the hash code    */
  418.         value *= S_MAX;
  419.     return (value);
  420. }
  421. usage()
  422. /*
  423.  * Help message
  424.  */
  425. {
  426.     register char        **hp;
  427.  
  428.     for (hp = helpmessage; *hp != NULL; hp++) {
  429.         fprintf(stderr, "%s\n", *hp);
  430.     }
  431. }
  432.